/**
 * @file ZSTEdgeBuffer.h
 * @brief ZSuffixTree's edge hash
 * @author babear.wangz
 * @date 2011-04-06
 */

#ifndef ZST_EdgeBuffer_H
#define ZST_EdgeBuffer_H

#include "ZHashFunctions.h"
#include "ZTraits.h"
#include "ZSTEdgeAndNode.h"
#include "ZSTSequenceBuffer.h"

/**
 * @class ZSTEdgeBuffer
 * @brief suffix tree's edge buffer
 * @param NodeIdType id data type for node
 * @param EmitElemType element type
 * @param NodeIdHash hash function definition for Node type
 * @param SequenceClass sequence type
 * @param EmitElemHash hash function definition for sequence
 * @param SpaceParameter some parameters for space allocation
 * @author babear.wangz
 * @date 2011-04-06
 */
template <
    typename NodeIdType/* = uint32_t */,
    typename NodeIdHash/* = NodeIDHash<NodeIdType> */,
    typename EmitElemType/* = char */,
    typename SequenceClass/* = ZSTSequenceBuffer<EmitElemType> */,
    typename EmitElemHash/* = SequenceHash<EmitElemType> */,
    uint32_t WordLengthFunc(SequenceClass*, size_t),
    typename SpaceParameter = ZSTBufferSpaceParameter>
class ZSTEdgeBuffer {
public:
    typedef ZSTEdge<NodeIdType> EdgeType;//define the EdgeType
public:
    /**
     * @brief  explicit constructor
     * @param cap the initial space size for the hashtable of edges
     * @param seq the pointer for the sequence. in this class, we can get the
              characters which will be used in the hash computation from
              sequence by index.
     * @param nod the pointer for the suffix tree's nodes structure. we can
              modify the related node's first_edge information when we insert
              an edge into this edge buffer.
     * @author babear.wangz
     * @date 2011-04-13
     */
    explicit ZSTEdgeBuffer(SequenceClass* seq,
        ZSTSequenceBuffer<ZSTNode<NodeIdType> >* nod);
    explicit ZSTEdgeBuffer(uint32_t cap, SequenceClass* seq,
        ZSTSequenceBuffer<ZSTNode<NodeIdType> >* nod);
    // the destructor
    ~ZSTEdgeBuffer();
public:
    /**
     * @function Insert
     * @brief insert a new edge into the edge buffer. note that we don't allow
              to insert an existed edge or to cover one existed edge.
     * @param nid the starting node of the edge. if the edge is empty, it's -1
     * @param s   the starting index of the emitting word
     * @param e   the ending index of sequence in this edge. if ending is
                  unlimited, it's -1
     * @param enid the ending node of the edge. if the endnode is infinite,
                   it's -1
     ( @retirm
     * @author babear.wangz
     * @date 2011-04-13
     */
    bool Insert(NodeIdType nid, uint32_t s, uint32_t e, NodeIdType enid);

    /**
     * @function Find
     * @brief find the reference of a edge
     * @param nid the starting node of the edge
     * @param s   the starting index of the emitting word
     * @param pos the output, if the edge existed, it's the index of the edge
     * @return the reference of the edge
     * @author babear.wangz
     * @date 2011-04-13
     */
    EdgeType& Find(NodeIdType nid, uint32_t s, uint32_t& pos);

    // get the edge by its index
    inline EdgeType& GetEdge(uint32_t e_idx)
    {
        ASSERT(e_idx < capacity);
        return hashtable[e_idx];
    }
    // the swap
    void Swap(ZSTEdgeBuffer& edgebuf)
    {
        ::Swap(hashtable, edgebuf.hashtable);
        ::Swap(capacity, edgebuf.capacity);
        ::Swap(number, edgebuf.number);
        ::Swap(sequence, edgebuf.sequence);
        ::Swap(nodes, edgebuf.nodes);
    }
    void SwapWithNoSequenceAndNodes(ZSTEdgeBuffer& edgebuf)
    {
        ::Swap(hashtable, edgebuf.hashtable);
        ::Swap(capacity, edgebuf.capacity);
        ::Swap(number, edgebuf.number);
    }
private:
    DISALLOW_COPY_AND_ASSIGN(ZSTEdgeBuffer);
    // hash table for edges
    EdgeType* hashtable;
    // capacity
    uint32_t capacity;
    // number of element
    uint32_t number;
    // pointer to the sequence which the suffix tree rely on
    SequenceClass* sequence;
    // pointer to the suffix tree's nodes
    ZSTSequenceBuffer<ZSTNode<NodeIdType> >* nodes;
};

// constructor
template <
    typename NodeIdType, typename NodeIdHash, typename EmitElemType,
    typename SequenceClass, typename EmitElemHash,
    uint32_t WordLengthFunc(SequenceClass*, size_t),
    typename SpaceParameter>
ZSTEdgeBuffer<NodeIdType, NodeIdHash, EmitElemType, SequenceClass,
    EmitElemHash, WordLengthFunc, SpaceParameter>::ZSTEdgeBuffer(
        SequenceClass* seq,
        ZSTSequenceBuffer<ZSTNode<NodeIdType> >* nod)
: hashtable(0)
, capacity(0)
, number(0)
, sequence(seq)
, nodes(nod)
{
    capacity = SpaceParameter::ZSTEdgeBufferInitSize;
    hashtable = (EdgeType*)malloc(sizeof(EdgeType)*capacity);
    ASSERT(hashtable);
    for (uint32_t i = 0; i < capacity; ++i) {
        new (&hashtable[i]) EdgeType();
    }
}

// constructor
template <
    typename NodeIdType, typename NodeIdHash, typename EmitElemType,
    typename SequenceClass, typename EmitElemHash,
    uint32_t WordLengthFunc(SequenceClass*, size_t),
    typename SpaceParameter>
ZSTEdgeBuffer<NodeIdType, NodeIdHash, EmitElemType, SequenceClass,
    EmitElemHash, WordLengthFunc, SpaceParameter>::ZSTEdgeBuffer(
        uint32_t cap, SequenceClass* seq,
        ZSTSequenceBuffer<ZSTNode<NodeIdType> >* nod)
: hashtable(0)
, capacity(cap)
, number(0)
, sequence(seq)
, nodes(nod)
{
    if (capacity < SpaceParameter::ZSTEdgeBufferInitSize) {
        capacity = SpaceParameter::ZSTEdgeBufferInitSize;
    }
    hashtable = (EdgeType*)malloc(sizeof(EdgeType)*capacity);
    ASSERT(hashtable);
    for (uint32_t i = 0; i < capacity; ++i) {
        new (&hashtable[i]) EdgeType();
    }
}

//destructor
template <
    typename NodeIdType, typename NodeIdHash, typename EmitElemType,
    typename SequenceClass, typename EmitElemHash,
    uint32_t WordLengthFunc(SequenceClass*, size_t),
    typename SpaceParameter>
ZSTEdgeBuffer<NodeIdType, NodeIdHash, EmitElemType, SequenceClass,
    EmitElemHash, WordLengthFunc, SpaceParameter>::~ZSTEdgeBuffer()
{
    // fix me:
    for (uint32_t i = 0; i < capacity; ++i) {
        (hashtable + i)->~EdgeType();
    }
    free(hashtable);
}

// find the reference of an edge
template <
    typename NodeIdType, typename NodeIdHash, typename EmitElemType,
    typename SequenceClass, typename EmitElemHash,
    uint32_t WordLengthFunc(SequenceClass*, size_t),
    typename SpaceParameter>
ZSTEdge<NodeIdType>& ZSTEdgeBuffer<NodeIdType, NodeIdHash, EmitElemType,
    SequenceClass, EmitElemHash, WordLengthFunc, SpaceParameter>::Find(
        NodeIdType nid, uint32_t s, uint32_t& pos)
{
    uint32_t wlen = WordLengthFunc(sequence, s);
    unsigned seq_hash = EmitElemHash::Hash(&((*sequence)[s]), wlen);
    unsigned nod_hash = NodeIdHash::Hash(nid);
    uint64_t tmp = nod_hash;
    tmp = (tmp << 32) + seq_hash;
    unsigned hash_val = IntHash(tmp);
    pos = hash_val % capacity;
    while (!hashtable[pos].IsEmpty()) {
        if ((hashtable[pos].end == (uint32_t)(-1) ||
             hashtable[pos].end - hashtable[pos].start + 1 >= wlen) &&
            hashtable[pos].node == nid &&
            sequence->Equal(hashtable[pos].start, s, wlen)) {
            break;
        }
        pos = (pos+1) % capacity;
    }
    return hashtable[pos];
}

// insert an edge
template <
    typename NodeIdType, typename NodeIdHash, typename EmitElemType,
    typename SequenceClass, typename EmitElemHash,
    uint32_t WordLengthFunc(SequenceClass*, size_t),
    typename SpaceParameter>
bool ZSTEdgeBuffer<NodeIdType, NodeIdHash, EmitElemType, SequenceClass,
    EmitElemHash, WordLengthFunc, SpaceParameter>::Insert(
        NodeIdType nid, uint32_t s, uint32_t e,
        NodeIdType enid)
{
    ASSERT((e == (uint32_t)(-1)) || e+1 >= WordLengthFunc(sequence, s));
    if (double(number) >= double(capacity * 0.8)) {// need to expand
        uint32_t newcap = (uint32_t)((double)(capacity) * 
            SpaceParameter::ZSTEdgeBufferExtRate);
        ZSTEdgeBuffer newbuf(newcap, sequence, nodes);
        // clear nodes first edges
        for (uint32_t i = 0; i < nodes->Size(); ++i) {
            (*nodes)[i].first_edge = -1;
        }
        // rehash
        for (uint32_t i = 0; i < capacity; ++i) {
            if (!hashtable[i].IsEmpty()) {
                newbuf.Insert(hashtable[i].node,
                    hashtable[i].start,
                    hashtable[i].end,
                    hashtable[i].enode);
            }
        }
        Swap(newbuf);
    }
    uint32_t pos;
    EdgeType& edge = Find(nid, s, pos);
    if (edge.IsEmpty()) {
        edge.node = nid;
        edge.enode = enid;
        edge.start = s;
        edge.end = e;
        edge.next = (*nodes)[nid].first_edge;
        (*nodes)[nid].first_edge = pos;
        number ++;
        return true;
    } else {// we don't allow insert into a nonempty unit
        //ASSERT(false);
        return false;
    }
}

#endif

